package com.company.algo.tree;

import com.company.algo.pojo.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * 力扣第 652 题「寻找重复子树」
 * 1. 首先得知道以我为根的子树长什么样子（序列化） -- 后续遍历
 * 2. 然后得知道以其他节点为根的子树长什么样子  --HashSet
 *      如果出现多棵重复的子树，结果集res中必然出现重复，而题目要求不希望出现重复。
 *      HashSet升级成HashMap，额外记录每棵子树的出现次数：
 */
public class FindDuplicateSubtrees {
    HashMap<String,Integer> memo = new HashMap<>();
    LinkedList<TreeNode> res = new LinkedList<>();

    List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        serialize(root);
        return res;
    }

    String serialize(TreeNode root) {
        if (root == null) return "#";
        String left = serialize(root.left);
        String right = serialize(root.right);
        String subTree = left + "," + right + "," + root.val;
        int freq = memo.getOrDefault(subTree,0);
        if (freq == 1) res.add(root);
        memo.put(subTree,freq+1);
        return subTree;
    }
}
